package com.bing.java.stack;

import java.util.Iterator;

/**
 * 自定义栈
 * @author bing
 *
 *         2019年11月9日 下午2:56:27
 * 
 *         1. 数组实现
 */
public class ArrayStack<Item> implements MyStack<Item> {

	// 栈元素数组，只能通过转型来创建泛型数组
	@SuppressWarnings("unchecked")
	private Item[] a = (Item[]) new Object[1];

	// 元素数量
	private int N = 0;

	@Override
	public MyStack<Item> push(Item item) {    // push时候检查是否需要扩容数组
		check();
		a[N++] = item;						// 首次不需要扩容，直接将第一个元素放入数组栈，返回
		return this;
	}

	@Override
	public Item pop() throws Exception {

		if (isEmpty()) {                     // pop时候校验a数组size为0就是空
			throw new Exception("stack is empty");
		}

		Item item = a[--N];        //否则就移除一个，这里是将该数组对象设置为null。检查数组长度，适当减少

		check();

		// 避免对象游离
		a[N] = null;

		return item;
	}

	private void check() {

		if (N >= a.length) {
			resize(2 * a.length);

		} else if (N > 0 && N <= a.length / 4) {
			resize(a.length / 2);
		}
	}

	/**
	 * 调整数组大小，使得栈具有伸缩性
	 */
	private void resize(int size) {

		@SuppressWarnings("unchecked")
		Item[] tmp = (Item[]) new Object[size];

		for (int i = 0; i < N; i++) {
			tmp[i] = a[i];
		}

		a = tmp;
	}

	@Override
	public boolean isEmpty() {
		return N == 0;
	}

	@Override
	public int size() {
		return N;
	}

	@Override
	public Iterator<Item> iterator() {

		// 返回逆序遍历的迭代器
		return new Iterator<Item>() {

			private int i = N;

			@Override
			public boolean hasNext() {
				return i > 0;
			}

			@Override
			public Item next() {
				return a[--i];
			}
		};
	}
	
	public static void main(String[] args) {
		ArrayStack<Integer> arrayStack = new ArrayStack<Integer>();
		arrayStack.push(2);
		arrayStack.push(3);
	}
}
